﻿#define _CRT_SECURE_NO_WARNINGS 1
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
// 原题连接：https://leetcode.cn/problems/partition-list-lcci/submissions/
/*
题目描述：
给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
你不需要 保留 每个分区中各节点的初始相对位置。
*/


// Definition for singly-linked list.
 struct ListNode {
      int val;
      struct ListNode *next;
 };
 

// 方法1——使用额外的链表

struct ListNode* partition(struct ListNode* head, int x) {
    struct ListNode* LessHead = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* LessTail = NULL;
    struct ListNode* GreatHead = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* GreatTail = NULL;
    struct ListNode* cur = head;
    LessTail = LessHead;
    GreatTail = GreatHead;
    while (cur) {
        if (cur->val < x) {
            LessTail->next = cur;
            LessTail = LessTail->next;
        }
        else {
            GreatTail->next = cur;
            GreatTail = GreatTail->next;
        }
        cur = cur->next;
    }
    GreatTail->next = NULL;
    struct ListNode* newlesshead = LessHead;
    struct ListNode* newgreathead = GreatHead;
    LessTail->next = newgreathead->next;
    return newlesshead->next;
}

// 方法2——头插和尾插
/*
思路：
创建一个新的链表，然后将val小于x的节点进行头插，将val大于x的进行尾插。
*/

struct ListNode* partition(struct ListNode* head, int x) {
    struct ListNode* newhead = NULL;
    struct ListNode* cur = head;
    struct ListNode* pre = NULL; // 保存cur的前前一个节点
    struct ListNode* tail = NULL;
    while (cur) {
        pre = cur;
        cur = cur->next;
        if (pre->val < x) {
            // 头插
            if (NULL == newhead) {
                newhead = pre;
                tail = pre;
            }
            else {
                pre->next = newhead;
                newhead = pre;
            }
        }
        else {
            // 尾插
            if (NULL == newhead) {
                newhead = pre;
                tail = pre;
            }
            else {
                tail->next = pre;
                tail = tail->next;
            }
        }
    }
    if (tail) {
        tail->next = NULL;
    }
    return newhead;
}